// 返回合并后的链表头节点
package com.example.demo6;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class MyLinkedList<E extends Comparable> {
    // 封装一个链表
    Node<E> head = null;

    /**
     * 定义了一个私有的内部类,作为链表的结点
     */
    public static class Node<E> {
        E data;
        Node<E> next;

        public Node(E data, Node<E> next) {
            this.data = data;
            this.next = next;
        }
    }

    public Node<E> add(E e) {
        if (head == null) {
            head = new Node(e, null);
        } else {
            // 往后面插入结点（尾插法）
            Node<E> temp = head;
            // 让temp走到尾部结点
            while (temp.next != null) {
                temp = temp.next;
            }
            // 把当前结点创建出来,加入到尾部结点
            temp.next = new Node(e, null);
        }
        return head;
    }

    // 在MyLinkedList类中,开发一个sort方法,对两个链表分别排序,并分别遍历输出
    public Node<E> sort() {
        // 如果链表为空,直接返回头节点
        if (head == null) {
            return head;
        }

        // 创建一个ArrayList来存储链表中的数据
        List<E> number = new ArrayList<>();
        // 使用临时节点遍历链表,将链表中的数据添加到ArrayList中
        Node<E> temp = head; // 防止头指针被修改
        while (temp != null) {
            // 把遍历到的数据添加到集合中
            number.add(temp.data);
            temp = temp.next;
        }

        // 对ArrayList中的数据进行排序
        Collections.sort(number);

        // 使用另一个临时节点遍历链表,将排序后的数据重新赋值给链表节点
        Node<E> temp2 = head;
        for (E e : number) {
            temp2.data = e;
            temp2 = temp2.next;
        }
        // 返回链表的头节点
        return head;
    }

    /**
     * 遍历链表并打印每个节点的数据
     * 如果链表为空,则打印null并返回
     * 否则,从头节点开始,依次打印每个节点的数据,直到链表结束
     */
    public void forEach(Node<E> head) {
        // 检查链表是否为空
        if (head == null) {
            System.out.println(head);
            return;
        }
        // 初始化临时变量temp,用于遍历链表
        Node<E> temp = head;
        // 遍历链表,直到temp为null
        while (temp != null) {
            // 打印当前节点的数据
            System.out.print(temp.data + " ");
            // 将temp移动到下一个节点
            temp = temp.next;
        }
        // 打印换行,用于格式化输出
        System.out.println();
    }


    // 功能2：在MyLinkedList类中,开发一个mergeSort方法,支持将这两个升序排序的链表,合并成一个新链表,要求新链表中的节点仍然是递增排序的,
    // 然后对新链表遍历输出
    public Node<E> mergeSort(Node<E> head2) {
        // 如果两个链表都为空,则返回null
        if (head == null && head2 == null) {
            return null;
        }

        // 如果第一个链表为空,直接返回第二个链表头节点
        if (head == null && head2 != null) {
            return head2;
        }

        // 如果第二个链表为空,直接返回第一个链表头节点
        if (head != null && head2 == null) {
            return head;
        }

        // 如果两个链表都不为空,将第二个链表连接到第一个链表的末尾,然后进行排序
        // 这种方法的逻辑是,把第二个链表接到第一个链表的尾部,然后在统一进行排序即可
        /*if (head != null && head2 != null) {
            Node<E> temp = head;
            while (temp.next != null) {
                temp = temp.next;
            }
            // 连接第二个链表到第一个链表的末尾
            temp.next = head2;
            // 调用sort方法对连接后的链表进行排序
            sort();
        }*/

        if (head != null && head2 != null) {
            // 初始化一个新的链表头节点newHead,用于合并两个有序链表
            Node<E> newHead = new Node<>(null, null); // 新链表
            Node<E> newTemp = newHead;
            Node<E> temp1 = head;
            Node<E> temp2 = head2;
            // 遍历两个链表,将较小的节点添加到新链表中
            while (temp1 != null && temp2 != null) {
                // 比较两个链表当前节点的数据,将较小的节点链接到新链表
                if (temp1.data.compareTo(temp2.data) == -1) {
                    newHead.next = temp1;
                    temp1 = temp1.next;
                } else {
                    newHead.next = temp2;
                    temp2 = temp2.next;
                }
                newHead = newHead.next;
            }
            // 如果其中一个链表已经遍历完,将另一个链表剩余部分链接到新链表末尾
            if (temp1 == null) {
                newHead.next = temp2;
            }
            if (temp2 == null) {
                newHead.next = temp1;
            }
            // 更新head指向合并后的链表头节点
            head = newTemp.next;
        }
        return head;
    }
}